Method Of Complements
   HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
and
computing Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It includes the study and experimentation of algorithmic processes, and development of both hardware and software. Computing has scientific, e ...
, the method of complements is a technique to encode a symmetric range of positive and negative
integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
s in a way that they can use the same
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
(hardware) for
addition Addition (usually signified by the Plus and minus signs#Plus sign, plus symbol ) is one of the four basic Operation (mathematics), operations of arithmetic, the other three being subtraction, multiplication and Division (mathematics), division. ...
throughout the whole range. For a given number of
places Place may refer to: Geography * Place (United States Census Bureau), defined as any concentration of population ** Census-designated place, a populated area lacking its own municipal government * "Place", a type of street or road name ** Ofte ...
half of the possible representations of numbers encode the positive numbers, the other half represents their respective
additive inverse In mathematics, the additive inverse of a number is the number that, when added to , yields zero. This number is also known as the opposite (number), sign change, and negation. For a real number, it reverses its sign: the additive inverse (opp ...
s. The pairs of mutually additive inverse numbers are called ''complements''. Thus
subtraction Subtraction is an arithmetic operation that represents the operation of removing objects from a collection. Subtraction is signified by the minus sign, . For example, in the adjacent picture, there are peaches—meaning 5 peaches with 2 taken ...
of any number is implemented by adding its complement. Changing the sign of any number is encoded by generating its complement, which can be done by a very simple and efficient algorithm. This method was commonly used in
mechanical calculator A mechanical calculator, or calculating machine, is a mechanical device used to perform the basic operations of arithmetic automatically, or (historically) a simulation such as an analog computer or a slide rule. Most mechanical calculators wer ...
s and is still used in modern
computers A computer is a machine that can be programmed to carry out sequences of arithmetic or logical operations (computation) automatically. Modern digital electronic computers can perform generic sets of operations known as programs. These programs ...
. The generalized concept of the ''radix complement'' (as described below) is also valuable in
number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic function, integer-valued functions. German mathematician Carl Friedrich Gauss (1777â ...
, such as in
Midy's theorem In mathematics, Midy's theorem, named after French mathematician E. Midy, is a statement about the decimal expansion of fractions ''a''/''p'' where ''p'' is a prime and ''a''/''p'' has a repeating decimal expansion with an even period . If the p ...
. The ''nines' complement'' of a number given in decimal representation is formed by replacing each digit with nine minus that digit. To subtract a decimal number ''y'' (the
subtrahend Subtraction is an arithmetic operation that represents the operation of removing objects from a collection. Subtraction is signified by the minus sign, . For example, in the adjacent picture, there are peaches—meaning 5 peaches with 2 taken ...
) from another number ''x'' (the
minuend Subtraction is an arithmetic operation that represents the operation of removing objects from a collection. Subtraction is signified by the minus sign, . For example, in the adjacent picture, there are peaches—meaning 5 peaches with 2 taken ...
) two methods may be used: In the first method the nines' complement of ''x'' is added to ''y''. Then the nines' complement of the result obtained is formed to produce the desired result. In the second method the nines' complement of ''y'' is added to ''x'' and one is added to the sum. The leftmost digit '1' of the result is then discarded. Discarding the leftmost '1' is especially convenient on calculators or computers that use a fixed number of digits: there is nowhere for it to go so it is simply lost during the calculation. The nines' complement plus one is known as the ''ten's complement.'' The method of complements can be extended to other number bases ( radices); in particular, it is used on most digital computers to perform subtraction, represent negative numbers in base 2 or
binary arithmetic A binary number is a number expressed in the base-2 numeral system or binary numeral system, a method of mathematical expression which uses only two symbols: typically "0" (zero) and "1" (one). The base-2 numeral system is a positional notation ...
and test underflow and overflow in calculation.


Numeric complements

The radix complement of an n digit number y in
radix In a positional numeral system, the radix or base is the number of unique digits, including the digit zero, used to represent numbers. For example, for the decimal/denary system (the most common system in use today) the radix (base number) is t ...
b is defined as b^n - y. In practice, the radix complement is more easily obtained by adding 1 to the diminished radix complement, which is \left(b^n - 1\right) - y. While this seems equally difficult to calculate as the radix complement, it is actually simpler since \left(b^n - 1\right) is simply the digit b - 1 repeated n times. This is because b^n - 1 = (b - 1)\left(b^ + b^ + \cdots + b + 1\right) = (b - 1)b^ + \cdots + (b - 1) (see also Geometric series Formula). Knowing this, the diminished radix complement of a number can be found by complementing each digit with respect to b - 1, i.e. subtracting each digit in y from b - 1. The subtraction of y from x using diminished radix complements may be performed as follows. Add the diminished radix complement of x to y to obtain b^n - 1 - x + y or equivalently b^n - 1 - (x - y), which is the diminished radix complement of x-y. Further taking the diminished radix complement of b^n - 1 - (x - y) results in the desired answer of x - y. Alternatively using the radix complement, x-y may be obtained by adding the radix complement of y to x to obtain x + b^n - y or x - y + b^n. Assuming y \leq x , the result will be greater or equal to b^n and dropping the leading 1 from the result is the same as subtracting b^n, making the result x - y + b^n - b^n or just x - y, the desired result. In the
decimal The decimal numeral system (also called the base-ten positional numeral system and denary or decanary) is the standard system for denoting integer and non-integer numbers. It is the extension to non-integer numbers of the Hindu–Arabic numeral ...
numbering system, the radix complement is called the ''ten's complement'' and the diminished radix complement the ''nines' complement''. In
binary Binary may refer to: Science and technology Mathematics * Binary number, a representation of numbers using only two digits (0 and 1) * Binary function, a function that takes two arguments * Binary operation, a mathematical operation that t ...
, the radix complement is called the ''
two's complement Two's complement is a mathematical operation to reversibly convert a positive binary number into a negative binary number with equivalent (but negative) value, using the binary digit with the greatest place value (the leftmost bit in big- endian ...
'' and the diminished radix complement the ''
ones' complement The ones' complement of a binary number is the value obtained by inverting all the bits in the binary representation of the number (swapping 0s and 1s). The name "ones' complement" (''note this is possessive of the plural "ones", not of a sing ...
''. The naming of complements in other bases is similar. Some people, notably
Donald Knuth Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist, mathematician, and professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of computer sc ...
, recommend using the placement of the apostrophe to distinguish between the radix complement and the diminished radix complement. In this usage, the ''four's complement'' refers to the radix complement of a number in base four while ''fours' complement'' is the diminished radix complement of a number in base 5. However, the distinction is not important when the radix is apparent (nearly always), and the subtle difference in apostrophe placement is not common practice. Most writers use ''one's'' and ''nine's complement'', and many style manuals leave out the apostrophe, recommending ''ones'' and ''nines complement''.


Decimal example

The nines' complement of a decimal digit is the number that must be added to it to produce 9; the nines' complement of 3 is 6, the nines' complement of 7 is 2, and so on, see table. To form the nines' complement of a larger number, each digit is replaced by its nines' complement. Consider the following subtraction problem: 873
, the minuend The comma is a punctuation mark that appears in several variants in different languages. It has the same shape as an apostrophe or single closing quotation mark () in many typefaces, but it differs from them in being placed on the baseline ...
- 218 , the subtrahend


First method

Compute the nines' complement of the minuend, 873. Add that to the subtrahend 218, then calculate the nines' complement of the result. 126 ines' complement of x = 999 - x + 218 , the subtrahend ————— 344 99 - x + y Now calculate the nines' complement of the result 344 esult 655 ines' complement of 344 = 999 - (999 - x + y) = x - y, the correct answer


Second method

Compute the nines' complement of 218, which is 781. Because 218 is three digits long, this is the same as subtracting 218 from 999. Next, the sum of x and the nines' complement of y is taken: 873 + 781 ines' complement of y = 999 - y ————— 1654 99 + x - y The leading "1" digit is then dropped, giving 654. 1654 -1000
(999 + 1) 999 or triple nine most often refers to: * 999 (emergency telephone number), a telephone number for the emergency services in several countries * 999 (number), an integer * AD 999, a year * 999 BC, a year Books * ''999'' (anthology) or ''999: ...
————— 654 (999 + 1) + 999 + x - y This is not yet correct. In the first step, 999 was added to the equation. Then 1000 was subtracted when the leading 1 was dropped. So, the answer obtained (654) is one less than the correct answer x-y. To fix this, 1 is added to the answer: 654 + 1 ————— 655 - y Adding a 1 gives 655, the correct answer to our original subtraction problem. The last step of adding 1 could be skipped if instead the ten's complement of y was used in the first step.


Magnitude of numbers

In the following example the result of the subtraction has fewer digits than x: 123410
, the minuend The comma is a punctuation mark that appears in several variants in different languages. It has the same shape as an apostrophe or single closing quotation mark () in many typefaces, but it differs from them in being placed on the baseline ...
- 123401 , the subtrahend Using the first method the sum of the nines' complement of x and y is 876589 ines' complement of x + 123401 ———————— 999990 The nines' complement of 999990 is 000009. Removing the leading zeros gives 9 the desired result. If the subtrahend, y, has fewer digits than the minuend, x, leading zeros must be added in the second method. These zeros become leading nines when the complement is taken. For example: 48032 - 391 can be rewritten 48032 - 00391 with leading zeros Replacing 00391 with its nines' complement and adding 1 produces the sum: 48032 + 99608 ines' complement of y + 1 ——————— 147641 Dropping the leading 1 gives the correct answer: 47641.


Binary method

The method of complements is especially useful in binary (radix 2) since the ones' complement is very easily obtained by inverting each bit (changing '0' to '1' and vice versa). Adding 1 to get the two's complement can be done by simulating a carry into the least significant bit. For example: 0110 0100 , equals decimal 100 - 0001 0110 , equals decimal 22 becomes the sum: 0110 0100 + 1110 1001 nes' complement of y = 1111 1111 - y + 1 o get the two's complement = 1 0000 0000 - y ——————————— 10100 1110 + 1 0000 0000 - y Dropping the initial "1" gives the answer: 0100 1110 (equals decimal 78)


Negative number representations

The method of complements normally assumes that the operands are positive and that ''y'' ≤ ''x'', logical constraints given that adding and subtracting arbitrary integers is normally done by comparing signs, adding the two or subtracting the smaller from the larger, and giving the result the correct sign. Let's see what happens if ''x'' < ''y''. In that case, there will not be a "1" digit to cross out after the addition since x-y+b^n will be less than b^n. For example, (in decimal): 185 - 329 Complementing ''y'' and adding gives: 185 + 670 ines' complement of y + 1 ————— 856 At this point, there is no ''simple'' way to complete the calculation by subtracting b^n (1000 in this case); one cannot simply ignore a leading 1. The expected answer is −144, which isn't as far off as it seems; 856 happens to be the ten's complement of 144. This issue can be addressed in a number of ways: * Ignore the issue. This is reasonable if a person is operating a calculating device that doesn't support negative numbers since comparing the two operands before the calculation so they can be entered in the proper order, and verifying that the result is reasonable, is easy for humans to do. * Use the same method to subtract 856 from 1000, and then add a negative sign to the result. * Represent negative numbers as radix complements of their positive counterparts. Numbers less than b^n/2 are considered positive; the rest are considered negative (and their magnitude can be obtained by taking the radix complement). This works best for even radices since the sign can be determined by looking at the first digit. For example, numbers in ten's complement notation are positive if the first digit is 0, 1, 2, 3, or 4, and negative if 5, 6, 7, 8, or 9. And it works very well in binary since the first bit can be considered a sign bit: the number is positive if the sign bit is 0 and negative if it is 1. Indeed,
two's complement Two's complement is a mathematical operation to reversibly convert a positive binary number into a negative binary number with equivalent (but negative) value, using the binary digit with the greatest place value (the leftmost bit in big- endian ...
is used in most modern computers to represent signed numbers. * Complement the result if there is no carry out of the most significant digit (an indication that ''x'' was less than ''y''). This is easier to implement with
digital circuit In theoretical computer science, a circuit is a model of computation in which input values proceed through a sequence of gates, each of which computes a function. Circuits of this kind provide a generalization of Boolean circuits and a mathematical ...
s than comparing and swapping the operands. But since taking the radix complement requires adding 1, it is difficult to do directly. Fortunately, a trick can be used to get around this addition: Instead of always setting a carry into the least significant digit when subtracting, the carry out of the most significant digit is used as the carry input into the least significant digit (an operation called an ''
end-around carry In computing, signed number representations are required to encode negative numbers in binary number systems. In mathematics, negative numbers in any base are represented by prefixing them with a minus sign ("−"). However, in RAM or CPU regis ...
''). So if ''y'' ≤ ''x'', the carry from the most significant digit that would normally be ignored is added, producing the correct result. And if not, the 1 is not added and the result is one less than the radix complement of the answer, or the diminished radix complement, which does not require an addition to obtain. This method is used by computers that use sign-and-magnitude to represent signed numbers.


Practical uses

The method of complements was used in many mechanical calculators as an alternative to running the gears backwards. For example: * Pascal's calculator had two sets of result digits, a black set displaying the normal result and a red set displaying the nines' complement of this. A horizontal slat was used to cover up one of these sets, exposing the other. To subtract, the red digits were exposed and set to 0. Then the nines' complement of the minuend was entered. On some machine this could be done by dialing in the minuend using inner wheels of complements (i.e. without having to mentally determine the nines' complement of the minuend). In displaying that data in the complement window (red set), the operator could see the nines' complement of the nines' complement of the minuend, that is the minuend. The slat was then moved to expose the black digits (which now displayed the nines' complement of the minuend) and the subtrahend was added by dialing it in. Finally, the operator had to move the slat again to read the correct answer. * The
Comptometer The Comptometer was the first commercially successful key-driven mechanical calculator, patented in the United States by Dorr Felt in 1887. A key-driven calculator is extremely fast because each key adds or subtracts its value to the accumulato ...
had nines' complement digits printed in smaller type along with the normal digits on each key. To subtract, the operator was expected to mentally subtract 1 from the subtrahend and enter the result using the smaller digits. Since subtracting 1 before complementing is equivalent to adding 1 afterwards, the operator would thus effectively add the ten's complement of the subtrahend. The operator also needed to hold down the "subtraction cutoff tab" corresponding to the leftmost digit of the answer. This tab prevented the carry from being propagated past it, the Comptometer's method of dropping the initial 1 from the result. * The
Curta calculator The Curta is a hand-held mechanical calculator designed by Curt Herzstark. It is known for its extremely compact design: a small cylinder that fits in the palm of the hand. It was affectionately known as the "pepper grinder" or "peppermill ...
used the method of complements for subtraction, and managed to hide this from the user. Numbers were entered using digit input slides along the side of the device. The number on each slide was added to a result counter by a gearing mechanism which engaged cams on a rotating "echelon drum" (a.k.a. "step drum"). The drum was turned by use of a crank on the top of the instrument. The number of cams encountered by each digit as the crank turned was determined by the value of that digit. For example, if a slide is set to its "6" position, a row of 6 cams would be encountered around the drum corresponding to that position. For subtraction, the drum was shifted slightly before it was turned, which moved a different row of cams into position. This alternate row contained the nines' complement of the digits. Thus, the row of 6 cams that had been in position for addition now had a row with 3 cams. The shifted drum also engaged one extra cam which added 1 to the result (as required for the method of complements). The always present ten's complement "overflow 1" which carried out beyond the most significant digit of the results register was, in effect, discarded.


In computers

Use of the method of complements is ubiquitous in digital computers, regardless of the representation used for signed numbers. However, the circuitry required depends on the representation: * If two's complement representation is used, subtraction requires only inverting the bits of the subtrahend and setting a carry into the rightmost bit. * Using ones' complement representation requires inverting the bits of the subtrahend and connecting the carry out of the most significant bit to the carry in of the least significant bit (end-around carry). * Using sign-magnitude representation requires only complementing the sign bit of the subtrahend and adding, but the addition/subtraction logic needs to compare the sign bits, complement one of the inputs if they are different, implement an end-around carry, and complement the result if there was no carry from the most significant bit.


Manual uses

The method of complements was used to correct errors when accounting books were written by hand. To remove an entry from a column of numbers, the accountant could add a new entry with the ten's complement of the number to subtract. A bar was added over the digits of this entry to denote its special status. It was then possible to add the whole column of figures to obtain the corrected result. Complementing the sum is handy for cashiers making change for a purchase from currency in a single denomination of 1 raised to an integer power of the currency's base. For decimal currencies that would be 10, 100, 1,000, etc., e.g. a $10.00 bill.


In grade school education

In grade schools, students are sometimes taught the method of complements as a shortcut useful in
mental arithmetic Mental calculation consists of arithmetical calculations using only the human brain, with no help from any supplies (such as pencil and paper) or devices such as a calculator. People may use mental calculation when computing tools are not availab ...
.{{cite book , title = Principles of Arithmetic and Geometry for Elementary School Teachers , author = Carl Barnett Allendoerfer , publisher = Macmillan , year = 1971 Subtraction is done by adding the ten's complement of the
subtrahend Subtraction is an arithmetic operation that represents the operation of removing objects from a collection. Subtraction is signified by the minus sign, . For example, in the adjacent picture, there are peaches—meaning 5 peaches with 2 taken ...
, which is the nines' complement plus 1. The result of this addition is used when it is clear that the difference will be positive, otherwise the ten's complement of the addition's result is used with it marked as negative. The same technique works for subtracting on an adding machine.


See also

*
Two's complement Two's complement is a mathematical operation to reversibly convert a positive binary number into a negative binary number with equivalent (but negative) value, using the binary digit with the greatest place value (the leftmost bit in big- endian ...
– special case for binary computers


References

Computer arithmetic ja:補数